Holman có trận đấu đầu tiên cho đội tuyển Úc vào tháng 2 năm 2006 gặp Bahrain.[13]

Holman có tên trong danh sách 23 cầu thủ đội tuyển Úc tham dự World Cup 2010 tại Nam Phi.[14] Ngày 19 tháng 6 năm 2010, Holman ghi bàn mở tỉ số trong trận hòa 1-1 với Ghana tại trận đấu thứ hai vòng bảng khi ập vào sút bồi từ tình huống thủ môn Richard Kingson để bóng bật ra sau cú sút phạt của Marco Bresciano.[15] Ngày 24 tháng 6, anh có bàn thắng thứ hai tại giải đấu với cú sút ở cự ly 30m trong chiến thắng 2-1 trước Serbia.[16]

Holman sau đó tiếp tục có tên trong danh sách tham dự Cúp bóng đá châu Á 2011 tại Quatar. Anh ghi bàn trong trận đầu tiên thắng Ấn Độ 4-0.[17]

Năm 2013, sau khi kết thúc vòng loại World Cup 2014, Brett Holman giã từ sự nghiệp thi đấu quốc tế ở đội tuyển quốc gia sau 7 năm cống hiến.